//https://leetcode.cn/problems/word-ladder/

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> hash(wordList.begin(), wordList.end());
        unordered_set<string> vit;

        if (!hash.count(endWord)) return 0;
        if (beginWord == endWord) return 1;

        queue<string> q;
        q.push(beginWord);
        vit.insert(beginWord);
        int ret = 1;

        while (q.size())
        {
            ret++;

            int sz = q.size();
            while (sz--)
            {
                string s = q.front();
                q.pop();

                for (int i = 0; i < s.size(); i++)
                {
                    string temp = s;
                    for (char ch = 'a'; ch <= 'z'; ch++)
                    {
                        temp[i] = ch;

                        if (hash.count(temp) && !vit.count(temp))
                        {
                            if (temp == endWord) return ret;

                            q.push(temp);
                            vit.insert(temp);
                        }
                    }
                }
            }
        }

        return 0;

    }
};